#include <iostream>
#include <unordered_map>

using namespace std;

template<typename K, typename V>
class DNode
{
    public:
        K* m_pkey;
        V* m_pvalue;
        DNode<K, V>* m_pprev;
        DNode<K, V>* m_pnext;

        DNode(K* k=nullptr, V* v=nullptr, DNode<K, V>* prev=nullptr, DNode<K, V>* next=nullptr):m_pkey(k), m_pvalue(v), m_pprev(prev), m_pnext(next) {}

        ~DNode()
        {
            delete m_pkey;
            delete m_pvalue;
            m_pvalue = nullptr;
        }

        void update(V* v)
        {
            if(m_pvalue == nullptr) m_pvalue = new V(*v);
            else m_pvalue = v;
        }

        inline DNode<K, V>* prev(){return m_pprev;}
        inline DNode<K, V>* next(){return m_pnext;}
};

template<typename K, typename V>
class DList
{
    private:
        DNode<K, V>* m_phead = nullptr;
        DNode<K, V>* m_ptail = nullptr;
        int m_size = 0;

    public:

        ~DList()
        {
            while(m_phead)
            {
                auto temp = m_phead;
                m_phead = m_phead->m_pnext;
                delete temp;
            }
            m_ptail = m_phead = nullptr;
        }

        inline int size() const { return m_size; }

        void add_to_head(K&k, V& v)
        {
            auto node = new DNode<K, V>(new K(k), new V(v), nullptr, m_phead);
            add_to_head(node);
        }

        void add_to_head(DNode<K, V>* node)
        {
            if(m_phead != nullptr) m_phead->m_pprev = node;
            m_phead = node;
            if(m_ptail == nullptr) m_ptail = node;
            m_size++;
        }

        void add_to_tail(K& k, V& v)
        {
            auto node = new DNode<K, V>(new K(k), new V(v), m_ptail, nullptr);
            add_to_tail(node);
        }

        void add_to_tail(DNode<K, V>* node)
        {
            if(m_ptail != nullptr) m_ptail->m_pnext = node;
            m_ptail = node;
            if(m_phead == nullptr) m_phead = node;
            m_size++;
        }

        void remove_head(V& v)
        {
            if(m_phead)
            {
                auto node = m_phead;
                v = *(node->m_pvalue);
                m_phead = m_phead->m_pnext;
                m_size--;
                if(m_phead != nullptr) m_phead->m_pprev = nullptr;
                else m_ptail = nullptr;
                delete node;
            }
        }

        void remove_tail(V& v)
        {
            if(m_ptail)
            {
                auto node = m_ptail;
                v = *(node->m_pvalue);
                m_ptail = m_ptail->m_pprev;
                m_size--;
                if(m_ptail != nullptr) m_ptail->m_pnext = nullptr;
                else m_phead = nullptr;
                delete node;
            }
        }

        void remove_head()
        {
            V v;
            remove_head(v);
        }

        void remove_tail()
        {
            V v;
            remove_tail(v);
        }

        void tranvers_head() const
        {
            auto node = m_phead;
            while(node)
            {
                cout<<*(node->m_pvalue)<<" ";
                node = node->m_pnext;
            }
            cout<<endl;
        }

        void tranvers_tail() const
        {
            auto node = m_ptail;
            while(node)
            {
                cout<<*(node->m_pvalue)<<" ";
                node = node->m_pprev;
            }
            cout<<endl;
        }

        inline DNode<K, V>* head(){ return m_phead;}
        inline DNode<K, V>* tail(){ return m_ptail;}

        void remove(DNode<K, V>* node)
        {
            auto prev = node->prev();
            auto next = node->next();
            node->m_pprev = node->m_pnext = nullptr;
            if(prev != nullptr) prev->m_pnext = next;
            else m_phead = next;
            if(next != nullptr) next->m_pprev = prev;
            else m_ptail = prev;
            m_size--;
        }
};


template<typename K, typename V, int SIZE=1024>
class CLru
{
    public:
        bool get(const K& key, V& v)
        {
            auto it = m_map.find(key);
            if(it != m_map.end())
            {
                v = it->second->m_pvalue;
                m_list.remove(it->second);
                m_list.add_to_head(it->second);
            }
            return it != m_map.end();
        }

        void set(K& key, V&& v)
        {
            auto it = m_map.find(key);
            if(it == m_map.end())
            {
                m_list.add_to_head(key, v);
                m_map[key] = m_list.head();
                if(m_list.size() > SIZE)
                {
                    m_list.remove_tail();
                }
            }
            else
            {
                it->second->update(&v);
                m_list.remove(it->second);
                m_list.add_to_head(it->second);
            }
        }

        void tranvers_head() const {m_list.tranvers_head();}
        void tranvers_tail() const {m_list.tranvers_tail();}
        int size() const { return m_list.size(); }

    private:
        DList<K, V> m_list;
        unordered_map<K, DNode<K, V>*> m_map;
};

void test_dlist()
{
    DList<int, int> list;
    for(int i=1; i<=10; ++i) list.add_to_head(i, i);
    list.tranvers_head();
    list.tranvers_tail();
    list.remove_head();
    list.tranvers_head();
    list.tranvers_tail();
    list.remove_head();
    list.tranvers_head();
    list.tranvers_tail();
    list.remove_tail();
    list.tranvers_head();
    list.tranvers_tail();
}

void test_lru()
{
    CLru<int, int, 10> lru;
    for(int i = 0; i < 100; ++i)
    {
        lru.set(i, i+1);
        lru.tranvers_head();
        cout<<lru.size()<<endl;
    }
}


int main()
{
    for(int i = 0; i < 10; ++i) test_lru();
    return 0;
}

